package cn.cxq.learning.stack;

import org.junit.jupiter.api.Test;

import java.util.Stack;

/**
 * 剑指offer
 * 栈的压入、弹出序列
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：637342
 * 本题知识点： 栈
 *  算法知识视频讲解
 * 题目描述
 * 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
 * 假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，
 * 序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
 * （注意：这两个序列的长度是相等的）
 * 示例1
 * 输入
 * 复制
 * [1,2,3,4,5],[4,3,5,1,2]
 * 返回值
 * 复制
 * false
 */
public class PopOrder {

    @Test
    public void testIsPopOrder() {
        System.out.println(IsPopOrder(new int[]{1, 2, 3, 4, 5}, new int[]{2, 1, 3, 4, 5}));
    }


    public boolean IsPopOrder(int[] pushA, int[] popA) {

        if (pushA.length == 0 || popA.length == 0 || popA.length != pushA.length) {
            return false;
        }

        boolean is = true;

        Stack<Integer> stack = new Stack<>();

        int push = 0, pop = 0;


        while (pop != popA.length) {

            if (stack.empty()) {
                stack.push(pushA[push++]);
            }

            while (stack.peek() != popA[pop] && push != pushA.length) {
                stack.add(pushA[push++]);
            }
            if (stack.peek() != popA[pop]) {
                is = false;
                break;
            }
            stack.pop();
            pop++;
        }

        return is;
    }
}
